Travelling between cities

5

2 votes
Binary Search, DSU, Data Structures, Dynamic Programming, Medium, Merge Sort, Segment Trees
Problem

You are given positions of N cities situated on X axis. The position of the ith city is denoted by array value Location[i].You have a bike which can travel atmost K unit distance once the tank is full and each city has a fuel pump. You can assume that once the bike reaches a city its tank is again filled up completely.Now you have to answer Q queries where each query is of the following form.

  • LRX :- Find the number of cities lying in the index range [L,R] that you can reach from the city at index X.

Constraints:

  • 1T10
  • 1N,Q50000
  • 1K1000000
  • 1Locationi1000000000
  • 1LRN
  • 1XN

Note :- Use fast i/o.

Format of the input file:
First line : T i.e Number of testcases.
For each testcase :
First line : Three space separated integers N , K and Q.
Second line : N space separated integers denoting the location of cities .
Next Q lines : Three space separated LRX integers denoting the query.

Format of the output file:
Output the answer to each query in a separate line.

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

For second query you can reach all the cities from city with location 3(index 2) except the city with location 9(index 4) that lie in the range [1,5] of the array location[i]. Note that X , L and R are indexes of the array.

Editor Image

?